package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/*
题型：前序遍历 / 层次遍历
 https://leetcode.cn/problems/sum-of-left-leaves/description/
 https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html

 404. 左叶子之和
 给定二叉树的根节点 root ，返回所有左叶子之和。

 示例 1：
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:
输入: root = [1]
输出: 0
 */
class leetcode_404 {
    @Test
    fun test_1() {
        val n3 = TreeNode(3)
        val n9 = TreeNode(9)
        val n20 = TreeNode(20)
        val n15 = TreeNode(15)
        val n7 = TreeNode(7)
        n3.left = n9
        n3.right = n20
        n20.left = n15
        n20.right = n7

        val actual = sumOfLeftLeaves(n3)
        val expected = 24
        Assert.assertEquals(expected.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val root = TreeNode(1)
        val actual = sumOfLeftLeaves(root)
        val expected = 0
        Assert.assertEquals(expected.toString(), actual.toString())
    }

    private fun sumOfLeftLeaves(root: TreeNode?): Int {
        // 通过节点的父节点来判断其左孩子是不是左叶子了。
        // return sumOfLeftLeaves1(root)
        // sumOfLeftLeaves2(root)
        // return sum
        // return sumOfLeftLeaves3(root)
        return sumOfLeftLeaves4(root)
    }

    private fun sumOfLeftLeaves1(root: TreeNode?): Int {
        // 深度遍历 - 后序遍历 - 递归
        // T - N
        // S - H

        // 终止条件
        if (null == root) {
            return 0
        }
        if (root.left == null && root.right == null) {
            return 0
        }

        // 左
        var leftSum = sumOfLeftLeaves(root.left)
        root.left?.let {
            if (it.left == null && it.right == null) {
                leftSum += it.`val`
            }
        }
        // 右
        val rightSum = sumOfLeftLeaves(root.right)

        // 中
        val sum = leftSum + rightSum
        return sum
    }

    private var sum: Int = 0
    private fun sumOfLeftLeaves2(root: TreeNode?) {
        // 深度遍历 - 后序遍历 - 递归 (用一个成员变量sum去搜集结果，更好理解)
        // T - N
        // S - H

        // 终止条件
        if (null == root) {
            return
        }
        if (root.left == null && root.right == null) {
            return
        }

        // 左
        sumOfLeftLeaves(root.left)

        // 右
        sumOfLeftLeaves(root.right)

        // 中
        root.left?.let {
            if (it.left == null && it.right == null) {
                sum += it.`val`
            }
        }
    }


    private fun sumOfLeftLeaves3(root: TreeNode?): Int {
        // 深度遍历 - 后序 - 迭代方法 (统一写法)
        // 后序：左右中
        // 栈 ：中右左
        if (null == root) {
            return 0
        }

        var sum: Int = 0
        val stack: LinkedList<Pair<TreeNode, Boolean>> = LinkedList<Pair<TreeNode, Boolean>>()
        stack.push(Pair<TreeNode, Boolean>(root, false))

        while (!stack.isEmpty()) {
            val pair: Pair<TreeNode, Boolean> = stack.pop()
            val node: TreeNode = pair.first
            val visited: Boolean = pair.second

            // 收集结果
            if (visited) {
                node.left?.let {
                    if (it.left == null && it.right == null) {
                        sum += it.`val`
                    }
                }
                continue
            }
            // 中
            stack.push(Pair<TreeNode, Boolean>(node, true))
            // 右
            node.right?.let { stack.push(Pair<TreeNode, Boolean>(it, false)) }
            // 左
            node.left?.let { stack.push(Pair<TreeNode, Boolean>(it, false)) }
        }
        return sum
    }

    private fun sumOfLeftLeaves4(root: TreeNode?): Int {
        // 广度遍历 - 迭代
        // T - N
        // S - H

        if (null == root) {
            return 0
        }

        var sum: Int = 0
        val queue: LinkedList<TreeNode> = LinkedList<TreeNode>()
        queue.offer(root)
        while (!queue.isEmpty()) {
            var size: Int = queue.size

            while (size-- > 0) {
                val node = queue.poll()
                // 收集结果
                node.left?.let {
                    if (it.left == null && it.right == null) {
                        sum += it.`val`
                    }
                }
                node.left?.let { queue.offer(it) }
                node.right?.let { queue.offer(it) }
            }
        }
        return sum
    }

    fun sumOfLeftLeaves5(root: TreeNode?): Int {
        sum = 0
        collect(root)
        return sum
    }

    fun collect(root: TreeNode?) {
        // 深度遍历 - 前序遍历 - 递归
        // 1 确认函数参数以及返回值
        // 2 确认终止条件
        if (root == null) {
            return
        }
        // 3 确认单层递归的处理逻辑：前序遍历
        // 中
        root.left?.let {
            if (it.left == null && it.right == null) {
                sum = sum + it.`val`
            }
        }
        // 左
        collect(root.left)

        // 右
        collect(root.right)
    }
}